#include "libUnitTest/UnitTestPP.hpp"
#include "log.hpp"
#include <stdio.h>

int a[15] = {416, 763, 947, 951, 439, 297, 600, 981, 9, 788, 624, 631, 687, 1, 999};

namespace {
    // 插入排序算法
    void insertTest(int *array, int arrayLength)
    {
        int j, i, key;
        for (j = 1; j < arrayLength; j++) {
            key = array[j];
            for (i = j - 1; i >= 0; i--) {
                if (key < array[i]) {
                    array[i + 1] = array[i];
                    array[i] = key;
                }
            }
        }
    }

    // 分治法：将两个已经排序好的数组进行合并
    void merge(int *array, int arrayLength, int leftIdx, int rightIdx)
    {
        int leftLength = rightIdx - leftIdx;
        int rightLength = arrayLength - rightIdx;
        int *arrayLeft = (int *)malloc(sizeof(int) * leftLength + sizeof(int));
        int *arrayRight = (int *)malloc(sizeof(int) * rightLength + sizeof(int));
        int i, j, index;

        for (i = 0; i < leftLength; i++) {
            arrayLeft[i] = array[leftIdx + i];
        }
        arrayLeft[leftLength] = std::numeric_limits<int>::max();

        for (j = 0; j < rightLength; j++) {
            arrayRight[j] = array[rightIdx + j];
        }
        arrayRight[rightLength] = std::numeric_limits<int>::max();

        i = 0;
        j = 0;

        for (index = leftIdx; index < arrayLength; index++) {
            if (arrayLeft[i] > arrayRight[j]) {
                array[index] = arrayRight[j];
                if (j < rightLength) {
                    j++;
                }
            } else if (arrayLeft[i] <= arrayRight[j]) {
                array[index] = arrayLeft[i];
                if (i < leftLength) {
                    i++;
                }
            }
        }
        free(arrayLeft);
        free(arrayRight);
    }

    // 快速排序算法
    void quickSort(int *array, int arrayLength)
    {
        int middle = arrayLength / 2;
        if (middle <= 0) {
            return;
        }
        quickSort(array, middle);
        quickSort(array + middle, arrayLength - middle);
        merge(array, arrayLength, 0, middle);
    }

    // 冒泡排序
    void bubbleSort(int *array, int arrayLength)
    {
        int tmp = 0;
        int j;

        if (arrayLength < 1) {
            return;
        }

        for (j = 0; j < arrayLength - 1; j++) {
            if (array[j] > array[j + 1]) {
                tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;        
            }
        }

        bubbleSort(array, arrayLength - 1);
    }

    void printArrayElement(int *array, int arrayLength)
    {
        int i = 0;
        std::string logMsg;

        logMsg += "output:\n\t";
        for (i = 0; i < arrayLength; i++)
            logMsg += std::format("{} ", array[i]);
        logMsg += "\n";
        log(LOG_TRACE, logMsg);
    }

    TEST(insertSortTest)
    {
        insertTest(a, 15);
        printArrayElement(a, 15);    
    }

    TEST(quickSortTest)
    {
        quickSort(a, 15);
        printArrayElement(a, 15);  
    }

    TEST(bubbleSortTest)
    {
        quickSort(a, 15);
        printArrayElement(a, 15);
    }
}